package com.maltys.dp;

/**
 * ⼀个机器⼈位于⼀个 m x n ⽹格的左上⻆ （起始点在下图中标记为 “Start” ）。
 * 机器⼈每次只能向下或者向右移动⼀步。机器⼈试图达到⽹格的右下⻆（在下图中标记为 “Finish” ）。
 * 问总共有多少条不同的路径？
 *
 * @author malty
 * @link <a href="https://leetcode.cn/problems/unique-paths/description/">不同路径</a>
 */
public class DifferentPathII {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        if (obstacleGrid.length == 1 && obstacleGrid[0].length == 1) {
            return 1;
        }
        for (int i = 1; i < obstacleGrid.length; i++) {
            if (obstacleGrid[i][0] == 1) {
                while (i < obstacleGrid.length) {
                    obstacleGrid[i++][0] = 0;
                }
            } else {
                obstacleGrid[i][0] = 1;
            }
        }
        for (int i = 1; i < obstacleGrid[0].length; i++) {
            if (obstacleGrid[0][i] == 1) {
                while (i < obstacleGrid[0].length) {
                    obstacleGrid[0][i++] = 0;
                }
            } else {
                obstacleGrid[0][i] = 1;
            }
        }
        for (int i = 1; i < obstacleGrid.length; i++) {
            for (int j = 1; j < obstacleGrid[0].length; j++) {
                if (obstacleGrid[i][j] != 1) {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                } else {
                    obstacleGrid[i][j] = 0;
                }
            }
        }
        return obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }
}
